from typing import List


class Solution:
    _MOD = 10 ** 9 + 7

    def maxSumMinProduct(self, nums: List[int]) -> int:
        ans = 0

        stack = []  # 最小值、合计值
        for num in nums:
            min_val, sum_val = num, num
            sum_last_total = 0
            while stack and num < stack[-1][0]:
                min_last, sum_last = stack.pop()
                sum_last_total += sum_last
                ans = max(ans, min_last * sum_last_total)
            sum_val += sum_last_total

            if not stack or min_val > stack[-1][0]:
                stack.append([min_val, sum_val])
                ans = max(ans, stack[-1][0] * stack[-1][1])
            else:  # min_val == stack[-1][0]
                stack[-1][1] += sum_val
                ans = max(ans, stack[-1][0] * stack[-1][1])
            # print(stack)

        sum_last_total = 0
        while stack:
            min_last, sum_last = stack.pop()
            sum_last_total += sum_last
            ans = max(ans, min_last * sum_last_total)

        return ans % self._MOD


if __name__ == "__main__":
    print(Solution().maxSumMinProduct([1, 2, 3, 2]))  # 14
    print(Solution().maxSumMinProduct([2, 3, 3, 1, 2]))  # 18
    print(Solution().maxSumMinProduct([3, 1, 5, 6, 4, 2]))  # 60

    # 测试用例12
    print(Solution().maxSumMinProduct([2, 5, 4, 2, 4, 5, 3, 1, 2, 4]))  # 50

    # 测试用例38
    print(Solution().maxSumMinProduct([4, 10, 6, 4, 8, 7, 8, 3, 5, 3, 4, 9, 9, 5, 10, 7, 10, 7, 6, 4]))  # 387

    # 自制用例
    print(Solution().maxSumMinProduct([1, 6, 1, 4, 4, 4, 4]))  # 64
